package sortedArrayToBST

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
*/
func sortedArrayToBST(nums []int) *TreeNode {
	l := len(nums)
	mid := l / 2

	// 定义函数，返回已经构建好的子树，pos当前指针位置，left、right分别为子树下标的左右边界
	var sortTree func(pos, left, right int) *TreeNode

	sortTree = func(pos, left, right int) *TreeNode {
		// 确保子树不越界
		if pos < left || pos > right {
			return nil
		}
		node := &TreeNode{Val: nums[pos]}

		//中序遍历特点，根节点位于数组的中间
		node.Left = sortTree((left+pos)/2, left, pos-1)
		node.Right = sortTree((pos+right)/2+1, pos+1, right)
		return node
	}

	return sortTree(mid, 0, l-1)
}
